/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 徐海涛
 * Date: 2022-02-22
 * Time: 11:50
 */
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node(int val) {
        this.val = val;
    }
}
public class BinarySearchTree {
    public Node root = null;//根节点
    //查找key在不在二叉搜索树中
    public Node search(int key) {
        Node cur = root;
        while (cur != null) {
            //1.cur的值刚好等于key
            if(cur.val == key) {
                return cur;
            }else if(cur.val < key) {
                cur = cur.right;
            }else {
                cur = cur.left;
            }
        }
        return null;//代表没有这个数据
    }
    //二叉搜索树插入一个key
    //对于二叉搜索树来说，插入一个数据一定是叶子节点
    public boolean insert(int val) {
        //头节点为空
        if(root == null) {
            Node node = new Node(val);
            return true;
        }
        //如果头结点不为空那么就要去找叶子节点
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if(cur.val < val) {
                parent = cur;
                cur = cur.left;
            }else {
                parent = cur;
                cur = cur.right;
            }
        }
        Node node = new Node(val);//插入节点
        if(parent.val < val) {
            parent.right = node;
        }else {
            parent.left = node;
        }
        return true;
    }
    //二叉搜索树的删除
    public void remove(int key) {
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if(cur.val == key) {
                removeNode(cur,parent);
                break;
            }else if(cur.val < key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
    }
    //构造一个删除方法
    public void removeNode(Node cur,Node parent) {
        //第一种情况，cur.left == null;
        if(cur.left == null) {
            //1.如果cur == root
            if(cur == root) {
                root = cur.right;
                //2.如果 cur == parent.left
            }else if(cur == parent.left) {
                cur.left = parent.right;
                //3.如果 cur == parent.right
            }else {
                cur.right = parent.right;
            }
            //第二种情况 cur.right == null
        }else if(cur.right ==null) {
            //1.如果cur是root
            if(cur == root) {
                root = cur.left;
                //2,如果 cur = parent.left
            }else if(cur == parent.left) {
                cur.left = parent.left;
                //3.如果 cur = parent.right
            }else {
                parent.right = cur.left;
            }
            //第三种情况 cur.left != null && cur.right != null;
        }else {
            Node tap = cur;
            Node ta = cur.right;
            while (ta.left != null) {
                tap = ta;
                ta = tap.left;
            }
            cur.val = ta.val;
            if(tap.val == ta.val) {
                tap.left = ta.right;
            }else {
                tap.right = ta.right;
            }
        }
    }
}
